Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1 Output: [[12,21,16],[27,45,33],[24,39,28]]
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2 Output: [[45,45,45],[45,45,45],[45,45,45]]
m == mat.lengthn == mat[i].length1 <= m, n, K <= 1001 <= mat[i][j] <= 100
implSolution{pubfnmatrix_block_sum(mat:Vec<Vec<i32>>,k:i32) -> Vec<Vec<i32>>{let m = mat.len();let n = mat[0].len();let k = k asusize;letmut row_dp = vec![vec![0; n]; m];letmut answer = vec![vec![0; n]; m];for i in0..m { row_dp[i][0] = mat[i][..=(k.min(n - 1))].iter().sum();for j in1..n { row_dp[i][j] = row_dp[i][j - 1];if j - 1 >= k { row_dp[i][j] -= mat[i][j - 1 - k];}if j + k < n { row_dp[i][j] += mat[i][j + k];}}}for j in0..n { answer[0][j] = row_dp[..=(k.min(m - 1))].iter().map(|v| v[j]).sum();for i in1..m { answer[i][j] = answer[i - 1][j];if i - 1 >= k { answer[i][j] -= row_dp[i - 1 - k][j];}if i + k < m { answer[i][j] += row_dp[i + k][j];}}} answer }}